package com.sinaapp.gavinzhang.first;

/**
 * 堆排序
 * Created by gavin on 15-8-30.
 */
public class HeapSort {


    public static void main(String[] args)
    {
        int[] numbers = {4,6,2,5,1,3,8,7,9,10};
        HeapAdjust(numbers,0,numbers.length);
        HeapSort(numbers,numbers.length-1);
        for (int i : numbers)
        {
            System.out.print(i+" ");
        }
    }

    public static void HeapSort(int[] numbers,int h)
    {
        if (h == 0)return;
        numbers[0] ^= numbers[h];
        numbers[h] ^= numbers[0];
        numbers[0] ^= numbers[h];
        HeapAdjust(numbers, 0, h);
        HeapSort(numbers,h-1);
    }

    public static void HeapInit(int[] numbers)
    {
        int min = (numbers.length+1)/2 -1;

    }

    public static void HeapAdjust(int[] numbers,int h,int last)
    {
        for (int i=last/2-1; i>=h; i--)
        {
            if (i*2+2 == last)
            {
                if (numbers[i] < numbers[i*2+1])
                {
                    numbers[i] ^= numbers[i*2+1];
                    numbers[i*2+1] ^= numbers[i];
                    numbers[i] ^= numbers[i*2+1];
                    HeapAdjust(numbers,i,last);
                }
            }else {
                if (numbers[i*2+1] < numbers[i*2+2])
                {
                    if (numbers[i] < numbers[i*2+2])
                    {
                        numbers[i] ^= numbers[i*2+2];
                        numbers[i*2+2] ^= numbers[i];
                        numbers[i] ^= numbers[i*2+2];
                        HeapAdjust(numbers,i,last);
                    }
                } else
                {
                    if (numbers[i] < numbers[i*2+1])
                    {
                        numbers[i] ^= numbers[i*2+1];
                        numbers[i*2+1] ^= numbers[i];
                        numbers[i] ^= numbers[i*2+1];
                        HeapAdjust(numbers,i,last);
                    }
                }
            }
        }
    }
}
